import java.util.Arrays;

/**
 * @author dream
 * @date 2021/1/2 22:31
 */
public class Sort {
    /**
     *  选择排序
     */
    public static int[] selectionsort(int [] array){
        for (int i=0;i<array.length;i++){
            int minSeat=i;
            for (int j=i+1;j<array.length;j++){
                if (array[j]<array[minSeat]){
                    minSeat=j;
                }
            }
            interchange(array,minSeat,i);
        }
        return array;
    }

    /**
     * 插入排序
     */
    public static int[] insertionSorting(int [] array){
        for (int i=0;i<array.length;i++){
            int item=array[i];
            int j=i;

            while (j>0&&item<array[j-1]){
                array[j]=array[j-1];
                j--;
            }
            if (j!=i){
                array[j]=item;
            }
        }
        return array;
    }

    /**
     * 冒泡排序
     */
    public static int[] bubbleSort(int [] array){
        for (int i=1;i<array.length;i++){
            boolean isExchange=true;
            for (int j=0;j<array.length-i;j++){
                if (array[j]>array[j+1]){
                    interchange(array,j,j+1);
                    isExchange=false;
                }
            }
            if (isExchange){
                break;
            }
        }
        return array;

    }

    /**
     * 快速排序
     */
    public static int[] quickSort(int [] array){
        return quickSortRecursion(array,0,array.length-1);
    }

    private static int[] quickSortRecursion(int [] array,int left, int right){
        if (left<right){
            int partition = partition(array, left, right);
            quickSortRecursion(array, left, partition - 1);
            quickSortRecursion(array, partition + 1, right);
        }
        return array;
    }

    private static int partition(int[] array, int left, int right){
        int index= left +1;
        for (int i = index; i <= right; i++) {
            if (array[i] < array[left]) {
                interchange(array, i, index);
                index++;
            }
        }
        interchange(array, left, index - 1);
        return index - 1;
    }

    /**
     * 归并排序
     */
    public static int[] mergeSort(int [] array){
        return mergeSortRecursion(array);
    }

    private static int[] mergeSortRecursion(int [] array){
        if (array.length<2){
            return array;
        }
        int middle = (int) Math.floor(array.length / 2);
        int [] left= Arrays.copyOfRange(array,0,middle);
        int [] right= Arrays.copyOfRange(array,middle,array.length);
        return merge(mergeSortRecursion(left),mergeSortRecursion(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }


    /**
     * 希尔排序
     */
    public static int[] shellSort(int [] array){
        int length = array.length;
        int item;
        for (int step=length/2;step>=1;step/=2){
            for (int i=step;i<length;i++){
                item=array[i];
                int j=i-step;
                while (j>=0 &&array[j]>item){
                    array[j+step]=array[j];
                    j-=step;
                }
                array[j+step]=item;
            }
        }
        return array;
    }

    /**
     * 交换位置
     */
    private static void interchange(int [] array,int place1,int place2){
        if (place1 !=place2){
            int item = array[place1];
            array[place1] = array[place2];
            array[place2] = item;
        }
    }

}